import java.util.ArrayList;
import java.util.Collections;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Set;
import java.util.Comparator;


public class AStar {
	
	private Hashtable<Noeud, Integer> f;
	private Hashtable<Noeud, Integer> g;
	private Hashtable<Noeud, Noeud> predecesseur;
	private Noeud initial, terminal,x;
	private ArrayList<Noeud> ouverts,fermes;
	
	public AStar(Noeud s, Noeud t){
		f = new Hashtable<Noeud, Integer>();
		g = new Hashtable<Noeud, Integer>();
		
		initial = s;
		terminal = t;
	}
	
	public ArrayList<Noeud> a_star(){
		ouverts = new ArrayList<Noeud>();
		fermes = new ArrayList<Noeud>();
		ouverts.add(initial);
		g.put(initial, 0);
		f.put(initial, initial.getDistance_cible());
		predecesseur = new Hashtable<Noeud, Noeud>();
		
		while(ouverts.size() != 0){
			x = noeud_de_arc_minimal(ouverts);
			fermes.add(x);
			ouverts.remove(x); // A verif
			
		
			if(x == terminal){
				ArrayList<Noeud> tabRetour =  new ArrayList<Noeud>();
				tabRetour.add(terminal);
				tabRetour.addAll(trajet(terminal,new ArrayList<Noeud>()));
				Collections.reverse(tabRetour);
				return tabRetour;
			}

			
			
			Set<Noeud> set = x.successeur().keySet();
			Noeud node;

		    Iterator<Noeud> itr = set.iterator();
		    while (itr.hasNext()) {
		      node = itr.next();
		      if((ouverts.contains(node) == false) && (fermes.contains(node) == false)){
		    	  predecesseur.put(node, x);
		    	  //System.out.println(node.getNomVille()+" predecesseur de "+x.getNomVille());
		    	  ouverts.add(node);
		    	  g.put(node, (g.get(x))+x.distance_avec(node));
		    	  f.put(node, (g.get(node))+node.getDistance_cible());
		      }else{
		    	  if(g.get(node)>g.get(x)){
		    		  g.put(node, (g.get(x))+x.distance_avec(node));
			    	  f.put(node, (g.get(node))+node.getDistance_cible());
			    	  if(fermes.contains(node)){
			    		  ouverts.add(node);
			    		  fermes.remove(node);
			    	  }
		    	  }
		      }
		      
		      
		    }
			
		}
		return null;
		
	}
	
	private Noeud noeud_de_arc_minimal(ArrayList<Noeud> tab){
		return Collections.min(tab,
			new Comparator< Noeud >() {
				public int compare(Noeud a, Noeud b) {
					return ((Integer)(a.getDistance_cible()+ f.get(a))).compareTo(b.getDistance_cible()+f.get(b));
					}
				});
	}
	
	private ArrayList<Noeud> trajet(Noeud ville, ArrayList<Noeud> tab) {
		if(predecesseur.get(ville) == null) return tab;
		
		tab.add(predecesseur.get(ville));
		return trajet(predecesseur.get(ville), tab);
		
	}
}
